package com.atguigu.dynamic;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-05-27-14:48
 */


/*
* 1.将大问题分成小问题进行解决，从而一步步获取最优解的处理算法
* 2.动态规划与分治算法相类似，基本思想是将待解决的问题分解为若
*   干个子问题，先求解子问题，然后从这些子问题的解获得原问题的解
* 3.与分治算法不同，适合用于动态规划求解的问题，经分解得到子问题往往不是相互独立的
*   （即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步求解）
* 4.动态规划可以采用填表的方式逐步来推进，得到最优解。
* */
public class KanpspackProblem {
    public static void main(String[] args) {
        int[] val={1500,3000,2000};//表示物品的价值
        int[] w={1,4,3};//表示物品的重量
        int m=5;//表示背包的最大容量
        //创建一个二维数组来存放最大的结果
        int[][] v=new int[val.length+1][m+1];
        //创建一个二维数组存储我们存放的内容
        int[][] path=new int[val.length+1][m+1];
        //第一行和第一列已经默认设置为了0
        //往容器里面添加商品v[i][j]表示往容量为j的容器里面添加i及之前的商品所能添加的最大价值
        for (int i = 1; i < v.length; i++) {//不处理第一行 i是从1开始的
            for (int j = 1; j <v[0].length ; j++) {//j表示当前背包的容量
                if(w[i-1]>j){// 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
                    v[i][j]=v[i-1][j];
                }else{
                    //说明:
                    //因为我们的i 从1开始的， 因此公式需要调整成
                    //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
                    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
                    if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        path[i][j]=1;
                    }else{
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }
        //展示我们的容器在各个容量下存储的最大价值
        for (int[] res:v) {
            System.out.println(Arrays.toString(res));
        }
        //展示背包存储的内容
        int i = path.length-1;
        int j = path[i].length-1;
        while (i>0&&j>0){
            if(path[i][j]==1){
                System.out.println("第"+i+"件商品放入了背包中");
                j-=w[i-1];
            }
            i--;
        }
    }
}
